package arithmetic1.search;

import java.util.Arrays;

/*
    斐波拉契(黄金分割)查找
 */
public class FibonacciSearch {
    public static void main(String[] args) {
        int arr[]={0,1,2,3,4,5,6,7,8,9};
        int index=fibonacciSearch(arr,0,arr.length-1,9);
        System.out.println(index);
    }

    //黄金分割查找
    public static int fibonacciSearch(int arr[],int start,int end,int key){
        //得到斐波拉契数列
        int f[]=fibonacci(20);
        if(start<=end){
            //将原数组的长度变成最近的斐波拉契数
            int length=end-start+1;
            int k=0;
            while(f[k]<length){
                k++;
            }
            //将元数扩容成f[k]-1长度的数组
            arr=Arrays.copyOf(arr,f[k]-1);
            //将补齐的数用原数组最后一位来填充
            for(int i=end;i<=arr.length-1;i++){
                arr[i]=arr[end];
            }
            //查找
            while (start<=end){
                int mid=start+f[k-1]-1;
                if(arr[mid]<key){   //向右查找
                    start=mid+1;
                    k-=2;
                }else if (arr[mid]>key){ //向左查找
                    end=mid-1;
                    k--;
                }else {
                    //默认将length-1当做最初的end值(只有一个完整的数组时才是如此)
                    if(mid>length-1){
                        return length-1;
                    }
                    return mid;
                }
            }
        }
        return -1;
    }

    //生成斐波拉契数列
    public static int[] fibonacci(int maxSize){
        int f[]=new int[maxSize];
        f[0]=1;
        f[1]=1;
        for(int i=2;i<maxSize-1;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f;
    }

}
